#ifndef __hash_h__
#define __hash_h__
#define  _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm> 
#include<queue>
#include<string>
#include<math.h>
#include<stack>
#include<vector>
using namespace std;
template<class k>
class hashfunc
{
public:
	size_t operator()(const k& key)
	{
		return (size_t)key;
	}
};
template<>
class hashfunc<string>//模板特化
{
public:
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (auto ch : key)
		{
			hash += ch;
			hash *= 131;
		}
		return hash;
	}
};
template<class t>//t代表的是类型
class hashnode
{
public:
	hashnode(const t& data):
		_data(data),
		_next(nullptr)
	{}
	t _data;
	hashnode* _next;
};

template<class k, class t,class hash, class Keyoft>
class hashtable;//声明

template<class k, class t, class ref, class ptr, class hash, class Keyoft>
struct hashiterator
{
	typedef hashnode<t> node;
	typedef hashtable<k, t, hash, Keyoft> Hashtable;
	typedef hashiterator<k, t, ref, ptr, hash, Keyoft> self;
	node* _node;
	const Hashtable* _ht;
	Keyoft keyoft;
	hash hs;
	hashiterator(node* nd, const Hashtable* ht) :
		_node(nd),
		_ht(ht)
	{}
	ref operator*()
	{
		return _node->_data;
	}
	ptr operator->()
	{
		return &(_node->_data);
	}
	bool operator==(const self& other)
	{
		return _node == other._node;
	}
	bool operator!=(const self& other)
	{
		return _node != other._node;
	}
	self& operator++() 
	{
		node* tmp = _node;
		if (_node->_next) _node = _node->_next;
		else
		{
			size_t hashi = hs(keyoft(_node->_data)) % _ht->_table.size();
			hashi++;
			while (hashi < _ht->_table.size())
			{
				if (_ht->_table[hashi])
				{
					_node = _ht->_table[hashi];
					break;
				}
				else hashi++;
			}
		}
		if(tmp==_node) _node = nullptr;
		return *this;
	}
};

template<class k,class t,class hash,class Keyoft>
class hashtable
{
public:
	typedef hashiterator<k, t, t&, t*, hash, Keyoft> Iterator;
	typedef hashiterator<k, t, const t&, const t*, hash, Keyoft> const_Iterator;
	typedef hashnode<t> node;
	vector<node*> _table;
	hashtable()
	{
		_table.resize(__stl_next_prime(0));
		_size = 0;
	}
	Iterator find(const k& key)
	{
		size_t hash0 = hs(key) % _table.size();
		node* pcur = _table[hash0];
		while (pcur != nullptr && keyoft(pcur->_data) != key)
			pcur = pcur->_next;
		return Iterator(pcur,this);
	}
	bool erase(const k& key)
	{
		size_t hash0 = hs(key) % _table.size();
		node* pcur = _table[hash0];
		node* prev = nullptr;
		while (pcur)
		{
			if (keyoft(pcur) == key)
			{
				if (prev == nullptr) // 删除头节点
					_table[hash0] = pcur->_next;
				else
					prev->_next = pcur->_next;
				delete pcur;
				_size--;
				return true;
			}
			prev = pcur;
			pcur = pcur->_next;
		}
		return false;
	}
	pair<Iterator, bool> insert(const t& kv)
	{
		Iterator it = find(keyoft(kv));
		if (it != end()) return { it,false };
		if (double(_size) / double(_table.size()) >= 1)//扩容
		{
			unsigned long newsize = __stl_next_prime(_table.size() + 1);
			hashtable<k, t, hash, Keyoft> newtable;
			newtable._table.resize(newsize);
			for (int i = 0; i < _table.size(); i++)
			{
				node* pcur = _table[i];
				while (pcur)
				{
					newtable.insert(pcur->_data);
					pcur = pcur->_next;
				}
			}
			_table.swap(newtable._table);
		}
		node* newnode = new node(kv);
		size_t hash0 = hs(keyoft(kv)) % _table.size();//头插
		newnode->_next = _table[hash0];
		_table[hash0] = newnode;
		_size++;
		return { Iterator(newnode,this),true };
	}
	Iterator begin()
	{
		for (int i = 0; i < _table.size(); i++)
			if (_table[i]) return Iterator(_table[i], this);
		return Iterator(nullptr, this);
	}
	Iterator end()
	{
		return Iterator(nullptr, this);
	}
	const_Iterator begin() const//成员函数后面的const是修饰的this指针指向的内容的，所以这里的this指针是const hashtable*类型的。
	{
		for (int i = 0; i < _table.size(); i++)
			if (_table[i]) return const_Iterator(_table[i], this);
		return const_Iterator(nullptr, this);
	}
	const_Iterator end() const 
	{
		return const_Iterator(nullptr, this);
	}
private:
	size_t _size = 0;
	hash hs;
	Keyoft keyoft;
	unsigned long __stl_next_prime(unsigned long n)
	{
		static const int __stl_num_prime = 28;
		static const unsigned long __stl_prime_list[__stl_num_prime] =
		{
			53, 97, 193, 389, 769,
			1543, 3079, 6151, 12289, 24593,
			49157, 98317, 196613, 393241, 786433,
			1572869, 3145739, 6291469, 12582917,25165843,
			50331653, 100663319, 201326611, 402653189,805306457,
			1610612741, 3221225473, 4294967291
		};
		const unsigned long* first = __stl_prime_list;
		const unsigned long* last = __stl_prime_list + __stl_num_prime;
		const unsigned long* pos = lower_bound(first, last, n);
		return pos == last ? *(last - 1) : *pos;
	}
};
#endif

